package 周赛;

import java.util.HashMap;
import java.util.Map;

//
//假设某一天，你访问 i 号房间。
//如果算上本次访问，访问 i 号房间的次数为 奇数 ，那么 第二天 需要访问 nextVisit[i] 所指定的房间，其中 0 <= nextVisit[i] <= i 。
//如果算上本次访问，访问 i 号房间的次数为 偶数 ，那么 第二天 需要访问 (i + 1) mod n 号房间。
// 题解： https://leetcode-cn.com/problems/first-day-where-you-have-been-in-all-the-rooms/solution/tui-dao-chu-gong-shi-fx-2fx-1-fnextvisit-fsh9/
public class 访问完所有房间的第一天 {

    public int firstDayBeenInAllRooms(int[] nextVisit) {
        int MOD = 1000000007;
        //表示到达第i个房间所需要的天数
        /* 从第i-1 个房间到第i个房间，需要两次。第一次 dp[i-1]-dp[nextVisit[i-1]]+1  第二次 dp[i-1]+1
        * 合起来就是  2*dp[i-1]-dp[nextVisit[i-1]]+2
        * **/
        long[] dp = new long[nextVisit.length];
        dp[0]=1;
        for (int i = 1; i < nextVisit.length; i++) {
            dp[i]=(MOD+2*dp[i-1]-dp[nextVisit[i-1]]+2)%MOD;
        }
        return (int)(dp[nextVisit.length-1]-1+MOD)%MOD;
    }
//    public int firstDayBeenInAllRooms(int[] nextVisit) {
//        //要访问的房间总数
//        int n=nextVisit.length;
//        int MOD=1000000007;
//        Map<Integer, Integer> map = new HashMap<>();
//        //房间号 访问次数
//        map.put(0,1);
//        //天数
//        int day=0;
//        //当前访问的房间号
////        int cur=0;
//        //接下来要访问的房间号
//        int next=nextVisit[0];
//        while (map.size()!=n){
//            map.put(next,map.getOrDefault(next,0)+1);
//            //偶数
//            if (map.get(next)%2==0)
//                next=(next+1)%n;
//            else
//                next=nextVisit[next];
//            day++;
//            day%=MOD;
//        }
//        return day;
//    }
}
